//给你一个 只包含正整数 的 非空 数组 nums 。请你判断是否可以将这个数组分割成两个子集，使得两个子集的元素和相等。 
//
// 
//
// 示例 1： 
//
// 
//输入：nums = [1,5,11,5]
//输出：true
//解释：数组可以分割成 [1, 5, 5] 和 [11] 。 
//
// 示例 2： 
//
// 
//输入：nums = [1,2,3,5]
//输出：false
//解释：数组不能分割成两个元素和相等的子集。
// 
//
// 
//
// 提示： 
//
// 
// 1 <= nums.length <= 200 
// 1 <= nums[i] <= 100 
// 
// Related Topics 动态规划 
// 👍 838 👎 0

/**
 * @author DaHuangXiao
 */
package leetcode.editor.cn;

import java.util.Collections;

public class PartitionEqualSubsetSum {
    public static void main(String[] args) {
        Solution solution = new PartitionEqualSubsetSum().new Solution();
        solution.canPartition(new int[]{1,5,11,5});
    }

    //leetcode submit region begin(Prohibit modification and deletion)
    class Solution {
        // 等和目标值为数组总和的一半
        // 然后就变成01背包问题，先nums后target,target反序
        public boolean canPartition(int[] nums) {
            int sum = 0;
            for (int num : nums) {
                sum += num;
            }
            if (sum % 2 != 0) {
                return false;
            }
            int target = sum / 2;
            boolean[] dp = new boolean[target+1];
            dp[0]=true;
            for (int num:nums){
                for (int i = target; i>=num; i--) {
                    dp[i]=dp[i] || dp[i-num];
                }
            }
            return dp[target];
//            boolean[][] dp = new boolean[nums.length][target + 1];
//            if (nums[0]<=target){
//                dp[0][nums[0]]=true;
//            }
//
//            for (int i = 1; i < nums.length; i++) {
//                for (int j = 0; j < target + 1; j++) {
//                    dp[i][j] = nums[i]==j || dp[i-1][j] || ((j>=nums[i]) && dp[i-1][j-nums[i]]);
//                }
//            }
//            return dp[nums.length-1][target];
        }
    }
//leetcode submit region end(Prohibit modification and deletion)

}